package year2024.month4;

import org.junit.jupiter.api.Assertions;
import org.junit.jupiter.api.Test;

public class OptimalDivision {

    @Test
    void test1() {
        Assertions.assertEquals("1000/(100/10/2)", optimalDivision(new int[]{1000, 100, 10, 2}));
    }

    @Test
    void test2() {
        Assertions.assertEquals("2/(3/4)", optimalDivision(new int[]{2, 3, 4}));
    }


    @Test
    void test3() {
        Assertions.assertEquals("6/(2/3/4/5)", optimalDivision(new int[]{6, 2, 3, 4, 5}));
    }

    /**
     * 553. 最优除法
     * 给定一正整数数组 nums，nums 中的相邻整数将进行浮点除法。例如， [2,3,4] -> 2 / 3 / 4 。
     * <p>
     * 例如，nums = [2,3,4]，我们将求表达式的值 "2/3/4"。
     * 但是，你可以在任意位置添加任意数目的括号，来改变算数的优先级。你需要找出怎么添加括号，以便计算后的表达式的值为最大值。
     * <p>
     * 以字符串格式返回具有最大值的对应表达式。
     * <p>
     * 注意：你的表达式不应该包含多余的括号。
     */
    public String optimalDivision(int[] nums) {

        StringBuilder equation = new StringBuilder();

        equation.append(nums[0]);

        if (nums.length == 1) {
            return equation.toString();
        }

        if (nums.length == 2) {
            return ""+nums[0]+"/"+nums[1];
        }

        equation.append("/(");

        float[] cache = new float[nums.length];
        StringBuilder[] equationCache = new StringBuilder[nums.length];
        float result = findMin(nums, 1, cache, equation, equationCache);

        System.out.println(nums[0] / result);

        return equation.append(")").toString();

    }

    float findMin(int[] nums, int currentIndex, float[] cache, StringBuilder equation, StringBuilder[] equationCache) {


        if (currentIndex == nums.length - 1) {

            equation.append(nums[currentIndex]);
            return nums[currentIndex];
        }

        float cachedVal = cache[currentIndex];
        StringBuilder cachedEquation = equationCache[currentIndex];
        if (cachedVal != 0) {
            System.out.printf("currentIndex=%d 缓存命中 %f\n", currentIndex, cachedVal);
            equation.append(cachedEquation);
            return cachedVal;
        }

        float min = Integer.MAX_VALUE;



        String finalEquation = "";

        float div = nums[currentIndex];
        StringBuilder divEquation = new StringBuilder().append(nums[currentIndex]);


        for (int i = currentIndex + 1; i < nums.length; i++) {

            StringBuilder subEquation = new StringBuilder();

            float remain = findMin(nums, i, cache, subEquation, equationCache);

            float quotient = div / remain; // 计算结果，商

            if (quotient < min) {

                min = quotient;

                /*if (i == currentIndex + 1) {
                    finalEquation = divEquation.toString() + "/" + subEquation.toString();
                } else {

                }*/
                String subEquationStr = subEquation.toString();
                if (subEquationStr.contains("/")) {
                    finalEquation = divEquation.toString() + "/(" + subEquationStr + ")";
                }else{
                    finalEquation = divEquation.toString() + "/" + subEquationStr ;
                }


                /*if (i != currentIndex + 1) {
                    finalEquation = "(" + finalEquation + ")";
                }*/
            }
            div = div / nums[i];

            divEquation.append("/").append(nums[i]);

        }

        equation.append(finalEquation);
        equationCache[currentIndex] = equation;
        return cache[currentIndex] = min;
    }
}
